package algorithm.dynamicProgramming;
//青蛙跳石头

/**
 * 题目：有n块石头分别放在x轴的0,1，…，n-1位置，一只青蛙在石头0，想要跳到石头n-1，
 *     若青蛙在第i块石头上，他最多可以向右跳距离ai，问青蛙能否跳到石头n-1。
 */
public class FrogJumpsStone {
    public static void main(String[] args) {
        System.out.println(ok(new int[]{3,2,1,0,4}));
    }

    public static boolean ok(int[] A){
        boolean[] f = new boolean[A.length];
        f[0] =true;

        for (int i = 1;i<A.length;i++){
            f[i] = false;
          for (int j = 0;j<i;j++){
              if (f[j] && j + A[j] >= i){
                  f[i] = true;
                  break;
              }
          }

        }
        return f[A.length-1];
    }
}
